home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / objtools / tlsplit.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  15KB  |  747 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    tlsplit -
  19.  *        Split all intersecting triangles in a triangle list.
  20.  *
  21.  *            Paul Haeberli - 1991
  22.  */
  23. #include "math.h"
  24. #include "stdio.h"
  25. #include "gl.h"
  26. #include "device.h"
  27. #include "trilist.h"
  28. #include "vect.h"
  29. #include "simple.h"
  30.  
  31. #define WSIZE        (200)
  32. #define ASPECT        (3.0/2.0)
  33. #define ALMOSTPLANAR    (0.9999)
  34.  
  35. #define USEDOUBLES
  36.  
  37. #ifdef USEDOUBLES
  38.  
  39. #define TOLERANCE        (0.00000000001)
  40. #define VECT            dvect
  41. #define FLOAT            double
  42. #define TRINORMAL(a,b,c,d,e)    dtrinormal(a,b,c,d,e)
  43. #define FLERP(a,b,c)        dlerp(a,b,c)
  44. #define VLERP(a,b,c,d)        dvlerp(a,b,c,d)
  45. #define VPLANE(a,b,c)        dvplane(a,b,c)
  46. #define V3F(a)            v3d((double *)a)
  47. #define VDOT(a,b)        dvdot(a,b)
  48.  
  49. #else
  50.  
  51. #define TOLERANCE        (0.0000001)
  52. #define VECT            vect
  53. #define FLOAT            float
  54. #define TRINORMAL(a,b,c,d,e)    trinormal(a,b,c,d,e)
  55. #define FLERP(a,b,c)        flerp(a,b,c)
  56. #define VLERP(a,b,c,d)        vlerp(a,b,c,d)
  57. #define VPLANE(a,b,c)        vplane(a,b,c)
  58. #define V3F(a)            v3f((float *)a)
  59. #define VDOT(a,b)        vdot(a,b)
  60.  
  61. #endif
  62.  
  63. typedef struct tile {
  64.     struct tile *next;    
  65.     FLOAT xmin, xmax;
  66.     FLOAT ymin, ymax;
  67.     FLOAT zmin, zmax;
  68.     VECT plane;
  69.     VECT edgeeq[3];
  70.     VECT pos[3];
  71.     long col[3];
  72.     int backfacing;
  73. } tile;
  74.  
  75. #define INTER_NONE    0
  76. #define INTER_TOUCHES    1
  77. #define INTER_COVERS    2
  78.  
  79. float frand();
  80. tile *tiles;
  81. FILE *outf;
  82. FLOAT curwidth;
  83. int ntiles;
  84. FLOAT cthresh;
  85.  
  86. tile *ysortlist();
  87. tile *splittri();
  88. FLOAT cdist();
  89. FLOAT colordel();
  90.  
  91. unsigned long clerp(i1,i2,param)
  92. unsigned long i1, i2;
  93. FLOAT param;
  94. {
  95.     int r1, g1, b1, a1;
  96.     int r2, g2, b2, a2;
  97.     int r, g, b, a;
  98.     unsigned long ret;
  99.  
  100.     r1 = (i1>>24)&0xff;
  101.     g1 = (i1>>16)&0xff;
  102.     b1 = (i1>>8)&0xff;
  103.     a1 = (i1>>0)&0xff;
  104.     r2 = (i2>>24)&0xff;
  105.     g2 = (i2>>16)&0xff;
  106.     b2 = (i2>>8)&0xff;
  107.     a2 = (i2>>0)&0xff;
  108.     r = lerp(r1,r2,param);
  109.     g = lerp(g1,g2,param);
  110.     b = lerp(b1,b2,param);
  111.     a = lerp(a1,a2,param);
  112.     ret = (r<<24)+(g<<16)+(b<<8)+(a<<0);
  113.     return ret;
  114. }
  115.  
  116. /*
  117.  *    fast alloc for tiles.
  118.  *
  119.  *
  120.  */
  121. #define NINCHUNK    300
  122.  
  123. tile *ftiles;
  124.  
  125. tile *tilemalloc()
  126. {
  127.     tile *t;
  128.     int i;
  129.  
  130.     if(!ftiles) {
  131.            t = (tile *)malloc(NINCHUNK*sizeof(tile));
  132.         for(i=0; i<NINCHUNK; i++)
  133.         freetile(t++);
  134.     }
  135.     t = ftiles;
  136.     ftiles = ftiles->next;
  137.     t->next = 0;
  138.     return t;
  139. }
  140.  
  141. freetile(t)
  142. tile *t;
  143. {
  144.    if( t ) {
  145.        t->next = ftiles;
  146.        ftiles = t;
  147.    }
  148. }
  149.  
  150. FLOAT edgedist2d(edgeeq,pos)
  151. VECT *edgeeq, *pos;
  152. {
  153.     return (edgeeq->x*pos->x) + (edgeeq->y*pos->y) + edgeeq->w;
  154. }
  155.  
  156. FLOAT planedist3d(planeeq,pos)
  157. VECT *planeeq, *pos;
  158. {
  159.     return (planeeq->x*pos->x) + 
  160.               (planeeq->y*pos->y) + 
  161.              (planeeq->z*pos->z) + planeeq->w;
  162. }
  163.  
  164. tile *readtilelist(name)
  165. char *name;
  166. {
  167.     int i, j, ntri;
  168.     trilisttri tri;
  169.     tile *tiles, *atile;
  170.     VECT norm, temp;
  171.     FLOAT dx, dy, w, mag;
  172.  
  173.     ntri = tlopen(name);
  174.     tiles = 0;
  175.     for(i=0; i<ntri; i++) {
  176.     tlread(&tri);
  177.     atile = tilemalloc();
  178.  
  179.     atile->pos[0].x = tri.x0;
  180.     atile->pos[0].y = tri.y0;
  181.     atile->pos[0].z = tri.z0;
  182.     atile->pos[1].x = tri.x1;
  183.     atile->pos[1].y = tri.y1;
  184.     atile->pos[1].z = tri.z1;
  185.     atile->pos[2].x = tri.x2;
  186.     atile->pos[2].y = tri.y2;
  187.     atile->pos[2].z = tri.z2;
  188.     atile->col[0] = tri.c0&0xffffff;
  189.     atile->col[1] = tri.c1&0xffffff;
  190.     atile->col[2] = tri.c2&0xffffff;
  191.     if(TRINORMAL(atile->pos+0,atile->pos+1,atile->pos+2,&norm,TOLERANCE/50.0)) {
  192.         if(norm.z<0.0) {
  193.         norm.x = -norm.x;
  194.         norm.y = -norm.y;
  195.         norm.z = -norm.z;
  196.         temp = atile->pos[1];
  197.         atile->pos[1] = atile->pos[2];;
  198.         atile->pos[2] = temp;
  199.         atile->backfacing = 1;
  200.         } else {
  201.         atile->backfacing = 0;
  202.         }
  203.         VPLANE(&norm,atile->pos+0,&atile->plane);
  204.         tiledomain(atile);
  205.  
  206.         atile->next = tiles;
  207.         tiles = atile;
  208.     } else {
  209.         fprintf(stderr,"zero tri found!!\n");
  210.     }
  211.     }
  212.     tlclose();
  213.     tiles = (tile *)ysortlist(tiles);
  214.     return tiles;
  215. }
  216.  
  217. tiledomain(atile)
  218. tile *atile;
  219. {
  220.     int j;
  221.     FLOAT dx, dy, w, mag;
  222.  
  223.     for(j=0; j<3; j++) {
  224.     dx = atile->pos[(j+1)%3].y-atile->pos[j].y;
  225.     dy = atile->pos[(j+1)%3].x-atile->pos[j].x;
  226.     mag = sqrt(dx*dx+dy*dy);
  227.     dx = dx/mag;
  228.     dy = -dy/mag;
  229.     w = dx*atile->pos[j].x+dy*atile->pos[j].y;
  230.     atile->edgeeq[j].x = dx;
  231.     atile->edgeeq[j].y = dy;
  232.     atile->edgeeq[j].w = -w;
  233.     }
  234.     atile->xmin = atile->xmax = atile->pos[0].x;
  235.     atile->ymin = atile->ymax = atile->pos[0].y;
  236.     atile->zmin = atile->zmax = atile->pos[0].z;
  237.     for(j=1; j<3; j++) {
  238.     if(atile->xmin>atile->pos[j].x)
  239.         atile->xmin=atile->pos[j].x;
  240.     if(atile->xmax<atile->pos[j].x)
  241.         atile->xmax=atile->pos[j].x;
  242.     if(atile->ymin>atile->pos[j].y)
  243.         atile->ymin=atile->pos[j].y;
  244.     if(atile->ymax<atile->pos[j].y)
  245.         atile->ymax=atile->pos[j].y;
  246.     if(atile->zmin>atile->pos[j].z)
  247.         atile->zmin=atile->pos[j].z;
  248.     if(atile->zmax<atile->pos[j].z)
  249.         atile->zmax=atile->pos[j].z;
  250.     }
  251. }
  252.  
  253. writetilelist(name,tiles)
  254. char *name;
  255. tile *tiles;
  256. {
  257.     trilisttri tltri;
  258.     short magic;
  259.     FILE *outf;
  260.  
  261.     outf = fopen(name,"w");
  262.     if(!outf) {
  263.     fprintf(stderr,"tlsplit: can't open output file\n");
  264.     exit(1);
  265.     }
  266.     magic = TLMAGIC;
  267.     fwrite(&magic,sizeof(short),1,outf);
  268.     while(tiles) {
  269.     tltri.x0 = tiles->pos[0].x;
  270.     tltri.y0 = tiles->pos[0].y;
  271.     tltri.z0 = tiles->pos[0].z;
  272.     tltri.c0 = tiles->col[0];
  273.     tltri.x1 = tiles->pos[1].x;
  274.     tltri.y1 = tiles->pos[1].y;
  275.     tltri.z1 = tiles->pos[1].z;
  276.     tltri.c1 = tiles->col[1];
  277.     tltri.x2 = tiles->pos[2].x;
  278.     tltri.y2 = tiles->pos[2].y;
  279.     tltri.z2 = tiles->pos[2].z;
  280.     tltri.c2 = tiles->col[2];
  281.     fwrite(&tltri,sizeof(trilisttri),1,outf);
  282.     tiles = tiles->next;
  283.     }
  284.     fclose(outf);
  285. }
  286.  
  287. drawtilelist(tlist)
  288. tile *tlist;
  289. {
  290.     reshapeviewport();
  291.     ortho(-1.1,1.1,-1.1,1.1,-2.0,2.0);
  292.     rgb(1.0,1.0,1.0);
  293.     clear();
  294.     rgb(1.0,0.0,0.0);
  295.     while(tlist) {
  296.     drawtile(tlist);
  297.     tlist = tlist->next;
  298.     }
  299. }
  300.  
  301. main(argc,argv)
  302. int argc;
  303. char **argv;
  304. {
  305.     short val;
  306.     int i;
  307.  
  308.     cthresh = 0.10;
  309.     if(argc<2) {
  310.     fprintf(stderr,"usage: tlsplit input.tl [-t 0.10]\n");
  311.     exit(1);
  312.     }
  313.     for(i=2; i<argc; i++) {
  314.     if(argv[i][0] == '-') {
  315.         switch(argv[i][1]) {
  316.         case 't':
  317.             i++;
  318.             cthresh = atof(argv[i]);
  319.             break;
  320.         }
  321.     }
  322.     }
  323.     prefposition(0,(3*WSIZE)-1,50,50+(2*WSIZE)-1);
  324.     foreground();
  325.     winopen("tlsplit");
  326.     qdevice(LEFTMOUSE);
  327.     qdevice(MIDDLEMOUSE);
  328.     RGBmode();
  329.     gconfig();
  330.     deflinestyle(1,0x3030);
  331.     rgb(0.5,0.5,0.5);
  332.     clear();
  333.     ntiles = 0;
  334.     tiles = readtilelist(argv[1]);
  335.     drawtilelist(tiles);
  336.     dosplit(tiles);
  337.     writetilelist(argv[2],tiles);
  338.     exit(0);
  339. }
  340.  
  341. printtile(t)
  342. tile *t;
  343. {
  344.     int i;
  345.  
  346.     for(i=0; i<3; i++) {
  347.     fprintf(stderr,"t%d: %f %f %f\n",
  348.                 i,t->pos[i].x,t->pos[i].y,t->pos[i].z);
  349.     }
  350.     fprintf(stderr,"\n");
  351. }
  352.  
  353. dosplit(tlist)
  354. tile *tlist;
  355. {
  356.     tile *tl, *otl, t1, t2, t3;
  357.     tile *stl, *ntl;
  358.     int interc;
  359.     FLOAT top;
  360.  
  361. /* use graphics for now */
  362.     reshapeviewport();
  363.     ortho(-1.0,1.0,-1.0,1.0,-2.0,2.0);
  364.     rgb(1.0,1.0,1.0);
  365.     clear();
  366.  
  367. /* find all the places where two triangles intersect */
  368.     rgb(0.0,0.0,0.0);
  369.     linewidth(1);
  370.     interc = 0;
  371.     tl = tlist;
  372.     while(tl) {
  373.     otl = tl;
  374.     while(otl->next) {
  375. #ifdef LATER
  376.         if(otl->next->ymin>tl->ymax)
  377.         break;
  378. #endif
  379.         if(tritriinter(tl,otl->next)) {
  380.         fprintf(stderr,"before split");
  381.         stl = splittri(otl->next,&tl->plane);
  382.         fprintf(stderr,"i");
  383.         if(stl) {
  384.             ntl = stl;
  385.             while(ntl->next) {
  386.             ntl = ntl->next;
  387.             fprintf(stderr,".");
  388.             }
  389.             ntl->next = otl->next;
  390.             otl->next = stl;
  391.             otl = ntl;
  392.         }
  393.         interc++;
  394.         }
  395.         otl = otl->next;
  396.     }
  397.     tl = tl->next;
  398.     }
  399.     fprintf(stderr,"\nTotal intersections %d\n",interc);
  400. }
  401.  
  402. #define E0    0x1
  403. #define E1    0x2
  404. #define E2    0x4
  405.  
  406. tile *splittri(try,plane)
  407. tile *try;
  408. VECT *plane;
  409. {
  410.     FLOAT pd[3], d, dp, dm, param;
  411.     tile *ret, *newl;
  412.     int intercode, vr;
  413.     int v0, v1, v2;
  414.     long ic0, ic1;
  415.     VECT ip0, ip1;
  416.  
  417.     dp = -plane->w;
  418.     dm = -plane->w;
  419.     d = -plane->w;
  420.  
  421.     pd[0] = VDOT(plane,&try->pos[0]);
  422.     pd[1] = VDOT(plane,&try->pos[1]);
  423.     pd[2] = VDOT(plane,&try->pos[2]);
  424.     ret = 0;
  425.     fprintf(stderr," p is %f vals are %f %f %f\n",d, pd[0],pd[1],pd[2]);
  426.     if(pd[0]<dp && pd[1]<dp && pd[2]<dp) {
  427.     fprintf(stderr,"bad poop1\n");
  428.     newl = tilemalloc();    
  429.     *newl = *try;
  430.     newl->next = 0;
  431.     return newl;
  432.     } else if(pd[0]>dm && pd[1]>dm && pd[2]>dm) {
  433.     fprintf(stderr,"bad poop2\n");
  434.     newl = tilemalloc();    
  435.     *newl = *try;
  436.     newl->next = 0;
  437.     return newl;
  438.     } else {
  439.     intercode = 0;
  440.     if(pd[0]<d && pd[1]>d) {
  441.         intercode |= E0;
  442.     } else if(pd[0]>d && pd[1]<d) {
  443.         intercode |= E0;
  444.     }
  445.     if(pd[1]<d && pd[2]>d) {
  446.         intercode |= E1;
  447.     } else if(pd[1]>d && pd[2]<d) {
  448.         intercode |= E1;
  449.     }
  450.     if(pd[2]<d && pd[0]>d) {
  451.         intercode |= E2;
  452.     } else if(pd[2]>d && pd[0]<d) {
  453.         intercode |= E2;
  454.     }
  455.     vr = 0;
  456.     switch(intercode) {
  457.         case E2:
  458.         vr++;
  459.         case E1:
  460.         vr++;
  461.         case E0:
  462.         v0 = (0+vr)%3;
  463.         v1 = (1+vr)%3;
  464.         v2 = (2+vr)%3;
  465.         param = (d-pd[v0])/(pd[v1]-pd[v0]);
  466.         VLERP(&try->pos[v0],&try->pos[v1],&ip0,param);
  467.         ic0 = clerp(try->col[v0],try->col[v1],param);
  468.  
  469.         newl = tilemalloc();        /* neg side */
  470.         newl->pos[v0] = try->pos[v0];
  471.         newl->col[v0] = try->col[v0];
  472.         newl->pos[v1] = ip0;
  473.         newl->col[v1] = ic0;
  474.         newl->pos[v2] = try->pos[v2];
  475.         newl->col[v2] = try->col[v2];
  476.         tiledomain(newl);
  477.         newl->plane = try->plane;
  478.         newl->next = ret;
  479.         ret = newl;
  480.  
  481.         newl = tilemalloc();        /* pos side */
  482.         newl->pos[v0] = ip0;    
  483.         newl->col[v0] = ic0;    
  484.         newl->pos[v1] = try->pos[v1];
  485.         newl->col[v1] = try->col[v1];
  486.         newl->pos[v2] = try->pos[v2];
  487.         newl->col[v2] = try->col[v2];
  488.         tiledomain(newl);
  489.         newl->plane = try->plane;
  490.         newl->next = ret;
  491.         ret = newl;
  492.  
  493.         return ret;
  494.         break;
  495.  
  496.         case E2|E0:
  497.         vr++;
  498.         case E1|E2:
  499.         vr++;
  500.         case E0|E1:
  501.         v0 = (0+vr)%3;
  502.         v1 = (1+vr)%3;
  503.         v2 = (2+vr)%3;
  504.         param = (d-pd[v0])/(pd[v1]-pd[v0]);
  505.         VLERP(&try->pos[v0],&try->pos[v1],&ip0,param);
  506.         ic0 = clerp(try->col[v0],try->col[v1],param);
  507.         param = (d-pd[v2])/(pd[v1]-pd[v2]);
  508.         VLERP(&try->pos[v2],&try->pos[v1],&ip1,param);
  509.         ic1 = clerp(try->col[v2],try->col[v1],param);
  510.  
  511.         newl = tilemalloc();        /* neg side */
  512.         newl->pos[v0] = try->pos[v0];
  513.         newl->col[v0] = try->col[v0];
  514.         newl->pos[v1] = ip0;
  515.         newl->col[v1] = ic0;
  516.         newl->pos[v2] = try->pos[v2];
  517.         newl->col[v2] = try->col[v2];
  518.         tiledomain(newl);
  519.         newl->plane = try->plane;
  520.         newl->next = ret;
  521.         ret = newl;
  522.  
  523.         newl = tilemalloc();        /* neg side */
  524.         newl->pos[v0] = ip0;
  525.         newl->col[v0] = ic0;
  526.         newl->pos[v1] = ip1;
  527.         newl->col[v1] = ic1;
  528.         newl->pos[v2] = try->pos[v2];
  529.         newl->col[v2] = try->col[v2];
  530.         tiledomain(newl);
  531.         newl->plane = try->plane;
  532.         newl->next = ret;
  533.         ret = newl;
  534.  
  535.         newl = tilemalloc();        /* pos side */
  536.         newl->pos[v0] = ip0;
  537.         newl->col[v0] = ic0;
  538.         newl->pos[v1] = try->pos[v1];
  539.         newl->col[v1] = try->col[v1];
  540.         newl->pos[v2] = ip1;
  541.         newl->col[v2] = ic1;
  542.         tiledomain(newl);
  543.         newl->plane = try->plane;
  544.         newl->next = ret;
  545.         ret = newl;
  546.  
  547.         return ret;
  548.         break;
  549.  
  550.         default:
  551.         fprintf(stderr,"strange code %d\n",intercode);
  552.         return ret;
  553.     }
  554.     }
  555. }
  556.  
  557. bbox3d(e,t)
  558. tile *e;
  559. tile *t;
  560. {
  561.     if(e->xmax<=t->xmin)
  562.     return 0;
  563.     if(t->xmax<=e->xmin)
  564.     return 0;
  565.     if(e->ymax<=t->ymin)
  566.     return 0;
  567.     if(t->ymax<=e->ymin)
  568.     return 0;
  569.     if(e->zmax<=t->zmin)
  570.     return 0;
  571.     if(t->zmax<=e->zmin)
  572.     return 0;
  573.     return 1;
  574. }
  575.  
  576. posinside(p,t)
  577. VECT *p;
  578. tile *t;
  579. {
  580.     int i;
  581.     FLOAT d;
  582.  
  583.     for(i=0; i<3; i++) {
  584.     d = edgedist2d(t->edgeeq+i,p);
  585.     if(d>-TOLERANCE)
  586.         return 0;
  587.     }
  588.     return 1;
  589. }
  590.  
  591. tritriinter(t1,t2)
  592. tile *t1, *t2;
  593. {
  594.     FLOAT d[3];
  595.     int i, l, g, il, ig, al, ag;
  596.     int lpos[3], gpos[3];
  597.     int ngood, ngot;
  598.     FLOAT goodparam[6], dot;
  599.     VECT *goodpos1[6], *goodpos2[6];
  600.     tile *goodtri[6];
  601.     VECT pos;
  602.  
  603.     if(!bbox3d(t1,t2))
  604.     return 0;
  605.     dot = VDOT(&t1->plane,&t2->plane);
  606.     if(dot<0.0)
  607.     dot = -dot;
  608.     if(dot>ALMOSTPLANAR) 
  609.          return 0;
  610.     ngood = 0;
  611.  
  612.     l = g = 0;
  613.     for(i=0; i<3; i++) {
  614.     d[i] = planedist3d(&t1->plane,&t2->pos[i]);
  615.     if(d[i]<-TOLERANCE) 
  616.         lpos[l++] = i;
  617.     else if(d[i]>TOLERANCE)
  618.         gpos[g++] = i;
  619.     }
  620.     if((l==0) || (g==0))
  621.      return 0;
  622.     for(il=0; il<l; il++) {
  623.     for(ig=0; ig<g; ig++) {
  624.         al = lpos[il];
  625.         ag = gpos[ig];
  626.         goodparam[ngood] = d[al]/(d[al]-d[ag]);
  627.         goodpos1[ngood] = &t2->pos[al];
  628.         goodpos2[ngood] = &t2->pos[ag];
  629.         goodtri[ngood] = t1;
  630.         ngood++;
  631.     }
  632.     }
  633.  
  634.     l = g = 0;
  635.     for(i=0; i<3; i++) {
  636.     d[i] = planedist3d(&t2->plane,&t1->pos[i]);
  637.     if(d[i]<-TOLERANCE) 
  638.         lpos[l++] = i;
  639.     else if(d[i]>TOLERANCE)
  640.         gpos[g++] = i;
  641.     }
  642.     if((l==0) || (g==0))
  643.      return 0;
  644.     for(il=0; il<l; il++) {
  645.     for(ig=0; ig<g; ig++) {
  646.         al = lpos[il];
  647.         ag = gpos[ig];
  648.         goodparam[ngood] = d[al]/(d[al]-d[ag]);
  649.         goodpos1[ngood] = &t1->pos[al];
  650.         goodpos2[ngood] = &t1->pos[ag];
  651.         goodtri[ngood] = t2;
  652.         ngood++;
  653.     }
  654.     }
  655.     ngot = 0;
  656.     for(g=0; g<ngood; g++) {
  657.     VLERP(goodpos1[g],goodpos2[g],&pos,goodparam[g]);
  658.     if(posinside(&pos,goodtri[g])) {    
  659.         ngot++;
  660.         if(ngot == 2) {
  661.         return 1;
  662.         } 
  663.     }
  664.     }
  665.     return 0;
  666. }
  667.  
  668. couldhide(e,t)
  669. tile *e;
  670. tile *t;
  671. {
  672.     if(t->zmax<=e->zmin)
  673.      return 0;
  674.     else
  675.      return 1;
  676. }
  677.  
  678. drawtile(t)
  679. tile *t;
  680. {
  681.     bgnclosedline();
  682.     V3F(t->pos+0);
  683.     V3F(t->pos+1);
  684.     V3F(t->pos+2);
  685.     endclosedline();
  686. }
  687.  
  688. compar(p0,p1)
  689. tile **p0, **p1;
  690. {
  691.     FLOAT y0, y1;
  692.  
  693.     y0 = (*p0)->ymin;
  694.     y1 = (*p1)->ymin;
  695.     if(y0<y1)
  696.     return 1;
  697.     if(y0==y1)
  698.     return 0;
  699.     else
  700.     return -1;
  701. }
  702.  
  703. tile *ysortlist(tiles)
  704. tile *tiles;
  705. {
  706.     tile *t, **all, **tpp;
  707.     int i, n;
  708.  
  709.     n = 0; 
  710.     t = tiles;
  711.     while(t) {
  712.     t = t->next;
  713.     n++;
  714.     }
  715.  
  716.     all = (tile **)malloc(n*sizeof(tile*));
  717.  
  718.     t = tiles;
  719.     tpp = all;
  720.     while(t) {
  721.     *tpp++ = t;
  722.     t = t->next;
  723.     }
  724.     qsort(all,n,sizeof(tile *),compar);
  725.  
  726.     t = 0;
  727.     tpp = all;
  728.     while(n--) {
  729.     (*tpp)->next = t;
  730.     t = *tpp++;
  731.     }
  732.  
  733.     free(all);
  734.     return t;
  735. }
  736.  
  737. dv3f(d)
  738. double d[3];
  739. {
  740.     float f[3];
  741.  
  742.     f[0] = d[0];
  743.     f[1] = d[1];
  744.     f[2] = d[2];
  745.     v3f(f);
  746. }
  747.